/**
 * Sort a linked list in O(n log n) time using constant space complexity.
 */

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* merge(struct ListNode* ptrA, struct ListNode* ptrB) {
    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->next = NULL;
    struct ListNode *cur = dummy;
    while(ptrA && ptrB) {
        if(ptrA->val < ptrB->val) {
            cur->next = ptrA;
            ptrA = ptrA->next;
        }
        else {
            cur->next = ptrB;
            ptrB = ptrB->next;
        }
        cur = cur->next;
    }
    if(ptrA) cur->next = ptrA;
    if(ptrB) cur->next = ptrB;
    return dummy->next;
}

struct ListNode* sortList(struct ListNode* head) {
    struct ListNode *ptrA, *ptrB, *curA, *curB, *sortedPtrA, *sortedPtrB, *sortedList;
    if(!head || !head->next) return head;
    ptrA = head;
    ptrB = head->next;
    curA = ptrA;
    curB = ptrB;
    while(curA && curB) {
        curA->next = curB->next;
        curA = curA->next;
        if(!curA) break;
        else {
            curB->next = curA->next;
            curB = curB->next;
        }
    }
    if(curA) curA->next = NULL;
    if(curB) curB->next = NULL;
    sortedPtrA = sortList(ptrA);
    sortedPtrB = sortList(ptrB);
    sortedList = merge(sortedPtrA, sortedPtrB);
    return sortedList;
}